package Top101K;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author quan
 * @Description 最长无重复子数组
 * @Date 2023/11/14 11:06
 */
public class BM92_MaxStrLength {
    public static void main(String[] args) {
        int[] arr = {2,3,4,3,5,6};
        //应该输出4,3,5，6
        int res = maxLength(arr);
        System.out.println(res);
    }

    /**
     * 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
     * 考点：map与滑动窗口
     * 所以right和left之间的区间一定就是最长不重复子数组
     * @param arr {2,3,3,4,3,5,6};
     * @return  4  [2,3,4]
     */
    public static int maxLength (int[] arr) {
        //1-定义一个map，用于存储指针所指位置的值和次数；
//        HashMap<Integer,Integer> map = new HashMap<>();
//        int max = 0;
//        //2-定义两个指针，初始化分别为第一个和第二个位置,都从数组开始位置
//        for (int left = 0,right = 0; right < arr.length; right++) {
//            //3-每次窗口都优先移动右边，记录当前值和出现次数
//            if(map.containsKey(arr[right])){
//                map.put(arr[right],map.get(arr[right])+1);
//            }else{
//                map.put(arr[right],1);
//            }
//            //4-一旦右指针所指值的次数》1，此时左指针需要右移缩减区间，同时移动一下就要从map中减少一下移动的元素的次数
//            //至于左指针移动到什么时候停止下来，是看右指针指的值的次数不再大于1了，就停止移动
//            while (map.get(arr[right])>1){
//                map.put(arr[left],map.get(arr[left])-1);
//                left++;
//            }
        //5-更新max值
//            max = Math.max(max,right-left+1);
//        }
//        return max;
        HashMap<Integer,Integer> map = new HashMap<>();
        int max = 0;
        for (int left = 0,right = 0; right < arr.length; right++) {
            if(!map.containsKey(arr[right])){
                map.put(arr[right],1);
            }else{
                map.put(arr[right],map.get(arr[right])+1);
            }
            while (map.get(arr[right])>1){
                map.put(arr[left],map.get(arr[left])-1);
                left++;
            }
            max = Math.max(max,right-left+1);
        }
        return max;
    }

//    ----------------------------自己写的下面这段代码与题目要求不符合------------------------------------------
    /**
     * 题目求得是最长不重复子数组，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。
     * 自己的思路刚开始就进行排序，已经打乱了这种题目要求，是不对的！
     * 自己求得是数组中的所有不重复元素的个数！
     * @param arr
     * @return
     */
//    public static int maxLength (int[] arr) {
//        if(arr.length == 2 && arr[0] == arr[1]){
//            return 1;
//        }
//        // write code here
//        //1-先对数组进行排序
//        Arrays.sort(arr);
//        //2-定义指针，从-0索引位置开始移动，只有下一个元素和当前所指的这个元素值不相同的时候，才添加下一个元素，否则指针继续移动到下一个位置
//        //所以指针指向的一定是不重复的元素
//        int i = 1;
//        int[] res = new int[arr.length];
//        res[0] = arr[0];
//        // res的指针
//        int k = 1;
//        int flag = 0;
//        while (i <= arr.length - 1) {
//            if (arr[flag] != arr[i]) {
//                res[k] = arr[i];
//                k++;
//                flag = i;
//            }
//            i++;
//        }
//
//        //3-res在初始化的时候是5的长度，最后存储的结果是{2,3,4,0,0}；
//        //所以这里要取出的是有元素的个数，而不直接是res的长度
//        int count = 0;
//        for (int j = 0; j < res.length; j++) {
//            System.out.println(res[j]);
//            if (res[j] == 0) {
//                count = j;
//                break;
//            } else {
//                count = res.length;
//            }
//        }
//        return count;
//    }
}
